//
//  插入排序.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/1.
//

import UIKit

class InsertSort: NSObject {
    static func sort(_ array: [Int]) -> [Int] {
        var array = array
        for begin in 1..<array.count {
            var current = begin
            for index in (0..<begin).reversed() {
                if array[index] > array[current] {
                    (array[index], array[current]) = (array[current], array[index])
                    current = index
                }
            }
        }
        return array
    }
// 优化1
    static func sort1(_ array: [Int]) -> [Int] {
        var array = array
        for begin in 1..<array.count {
            var current = begin
            let value = array[begin]
            while current > 0 && (array[current-1] > value) {
                array[current] = array[current-1]
                current -= 1
            }
            array[current] = value
        }
        return array
    }
    // 可以用二分查找、找到插入位置
    static func sort2(_ array: [Int]) -> [Int] {
        var array = array
        for begin in 1..<array.count {
            let insertValue = array[begin]
            let insetIndex = getErFen(array, index: begin)
            var index = begin
            while index<=begin && index > insetIndex {
                array[index] = array[index-1]
                index -= 1
            }
            array[insetIndex] = insertValue
        }
        return array
    }

    
    /// 通过二分搜索，获取插入位置
    /// - Parameters:
    ///   - array: 数组
    ///   - index: 元素
    /// - Returns: 返回的问题
    static func getErFen(_ array: [Int], index: Int) -> Int {
        var begin = 0
        var end = index
        let value = array[index]
        while begin < end {
            let mid = (begin + end) / 2
            if value < array[mid] {
                end = mid
            } else {
                begin = mid + 1
            }
        }
        return begin
    }
}
